package Tree;

import java.util.ArrayList;
import java.util.List;

public class item95 {
    public static List<TreeNode> generateTrees(int n) {
        if(n==0) return new ArrayList<>();
        List RES =build(1,n);
        return RES;
    }

    private static List build(int left, int right) {
        List<TreeNode> res = new ArrayList<>();
        if(left>right)
        {
            res.add(null);
            return res;
        }
        for (int i = left; i <=right ; i++) {
            List<TreeNode> l = build(left, i - 1);
            List<TreeNode> r = build(i + 1, right);
           for(TreeNode lt :l)
           {
               for(TreeNode rt:r)
               {
                   TreeNode root = new TreeNode(i);
                   root.left = lt;
                   root.right =rt;
                   res.add(root);
               }
           }
        }
        return res;
    }

    public static void main(String[] args) {
        generateTrees(3);
    }
}

